#pragma once

#include <set>

namespace Alice
{

class World;
using Entity = unsigned int;

/*
    四叉树的一个节点
    坐标基于 Transform 组件进行计算
*/
struct QuadTreeNode
{
    /*
        代表二维空间的矩形
        仅 QuadTreeNode 可用
        (left, top)     左上角坐标
        (right, bottom) 右下角坐标
    */
    struct Rect
    {
        float left, top, right, bottom;

        Rect() : left(0.0f), top(0.0f), right(0.0f), bottom(0.0f) {}

        Rect(float in_left, float in_top, float in_right, float in_bottom)
            : left(in_left), top(in_top), right(in_right), bottom(in_bottom) {}
    };


    // 判断当前节点是否叶子节点（是否已被划分）
    bool is_leaf;
    Rect rect;
    // 处于当前节点空间下的实体集合
    std::set<Entity> entitys;
    // 子节点，代表被划分的四个区域
    QuadTreeNode* left_top;
    QuadTreeNode* left_bottom;
    QuadTreeNode* right_top;
    QuadTreeNode* right_bottom;

    QuadTreeNode()
        : is_leaf(true), 
          left_top(nullptr), left_bottom(nullptr),
          right_top(nullptr), right_bottom(nullptr) {}

    QuadTreeNode(float left, float top, float right, float bottom)
        : is_leaf(true),
          left_top(nullptr), left_bottom(nullptr),
          right_top(nullptr), right_bottom(nullptr),
          rect({left, top, right, bottom}) {}
};

/*
    四叉树
    用来优化碰撞检测
*/
class QuadTree
{
public:
    QuadTree() : m_world(nullptr), m_root(nullptr) {}
    
    ~QuadTree() { __Destroy(m_root); }

    /*
        初始化四叉树的基本信息
    */
    inline void Init(World* world, unsigned int capacity)
    {
        m_world = world;
        m_capacity = capacity;
    }

    /*
        创建指定空间大小的四叉树
    */
    void Create(float left, float top, float right, float bottom);

    /*
        插入一个实体
    */
    void Insert(Entity entity);

    /*
        获得一个实体所在空间的所有实体（包括该实体本身）
    */
    std::set<Entity>& FindNeighbor(Entity entity);

private:
    /*
        向一个节点中插入一个实体
    */
    void __Insert(QuadTreeNode* node, Entity entity);

    /*
        检查一个实体是否属于给定的节点
    */
    bool __Check(QuadTreeNode* node, Entity entity);

    /*
        从一个节点下寻找对应实体
        返回和该实体处于同一空间的所有实体（包括该实体本身）
    */
    std::set<Entity>& __FindNeighbor(QuadTreeNode* node, Entity entity);

    /*
        销毁四叉树
        供析构调用
    */
    void __Destroy(QuadTreeNode* root);

    /*
        判断一个点在所给节点的象限
    */
    int __Quadrant(QuadTreeNode* node, float x, float y);

    /*
        对一个节点进行空间划分
        创建对应的子节点
    */
    void __Division(QuadTreeNode* node);

private:
    // 四叉树所属的世界
    World* m_world;
    // 四叉树中每个空间允许的最大容量
    unsigned int m_capacity;
    QuadTreeNode* m_root;
};

} // namespace Alice
